Universally Elevating the Phase Transition Performance of Compressed Sensing: Non-Isometric Matrices are Not Necessarily Bad Matrices

摘要

In compressed sensing problems, $\ell_1$ minimization or Basis Pursuit wasknown to have the best provable phase transition performance of recoverablesparsity among polynomial-time algorithms. It is of great theoretical andpractical interest to find alternative polynomial-time algorithms which performbetter than $\ell_1$ minimization. \cite{Icassp reweighted l_1}, \cite{Isitreweighted l_1}, \cite{XuScaingLaw} and \cite{iterativereweightedjournal} haveshown that a two-stage re-weighted $\ell_1$ minimization algorithm can boostthe phase transition performance for signals whose nonzero elements follow anamplitude probability density function (pdf) $f(\cdot)$ whose $t$-th derivative$f^{t}(0) \neq 0$ for some integer $t \geq 0$. However, for signals whosenonzero elements are strictly suspended from zero in distribution (for example,constant-modulus, only taking values `$+d$' or `$-d$' for some nonzero realnumber $d$), no polynomial-time signal recovery algorithms were known toprovide better phase transition performance than plain $\ell_1$ minimization,especially for dense sensing matrices. In this paper, we show that apolynomial-time algorithm can universally elevate the phase-transitionperformance of compressed sensing, compared with $\ell_1$ minimization, evenfor signals with constant-modulus nonzero elements. Contrary to conventionalwisdoms that compressed sensing matrices are desired to be isometric, we showthat non-isometric matrices are not necessarily bad sensing matrices. In thispaper, we also provide a framework for recovering sparse signals when sensingmatrices are not isometric.